//
// Created by DengLibin on 2019/1/11 0011.
//
/**
 * 合并 k 个排序链表，返回合并后的排序链表。请分析和描述算法的复杂度
 */
#include <iostream>
#include <vector>
using namespace std;
struct ListNode {
    int val;
    ListNode *next;
    ListNode(int x) : val(x), next(NULL) {}
};
ListNode* mergeKLists(vector<ListNode*>& lists) {
    ListNode * resNode = NULL; //返回结果
    ListNode * minNode = NULL; //记录集合中头节点最小的那个链表
    int index = 0; //头节点最小的那个链表的位置
    for(int i = 0; i < lists.size(); i++){
        if(lists[i] == NULL){ //跳过空的
            continue;
        }
        if(minNode == NULL || minNode->val > lists[i]->val){
            minNode = lists[i];
            index = i;
        }
    }

    resNode = minNode;
    if(resNode == NULL){ //到最后一个了
        return resNode;
    }
    lists[index] = minNode->next; //去除头节点
    resNode->next = mergeKLists(lists); //递归
    return resNode;

}


int main57(){
    ListNode l1(1);
    ListNode l2(2);
    ListNode l3(4);
    l1.next = &l2;
    l2.next = &l3;

    ListNode l4(1);
    ListNode l5(3);
    ListNode l6(4);
    l4.next = &l5;
    l5.next = &l6;
    vector<ListNode *> v;
    v.push_back(&l1);
    v.push_back(&l4);
    ListNode* head =  mergeKLists(v);
    ListNode * temp = head;
    while(temp != NULL){
        cout <<temp->val<<",";
        temp = temp->next;
    }

    return 0;
}